﻿#pragma once
#include <iostream>
using namespace std;

namespace key {
	template <class K> //因为键值参与比较，所以改名为K(Key)
	struct BSTreeNode { //数组只适合表示完全二叉树
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		BSTreeNode(const K& key)
			: _left(nullptr)
			, _right(nullptr)
			, _key(key) {
		}
	};

	template <class K>
	class BSTree {
		typedef BSTreeNode<K> Node;
	public:
		//bool Insert(const K& key) {
		//	if (_root == nullptr) {
		//		_root = new Node(key);
		//		return true;
		//	}
		//	//不为空找插入位置
		//	//比当前根节点小，走左边；比当前根节点大，走右边。直到节点为空
		//	Node* cur = _root;
		//	while (cur) {
		//		if (key > cur->_key) //比当前根节点大，走右边。
		//			cur = cur->_right;
		//		else if (key < cur->_key) //比当前根节点小，走左边
		//			cur = cur->_left;
		//		else
		//			return false; //默认二叉搜索树不允许重复值
		//	}
		//	cur = new Node(key);
		//	//这里虽然new了节点，但并未链接。
		//	//二叉树的链接是要父节点指向子节点。
		//	return true;
		//}
		//为了解决上述问题还需要一个父节点指针，
		//cur往后遍历之前，父节点指向cur节点
		bool Insert(const K& key) {
			if (_root == nullptr) {
				_root = new Node(key);
				return true;
			}
			//不为空找插入位置
			//比当前根节点小，走左边；比当前根节点大，走右边。直到节点为空
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				parent = cur; //cur往后遍历之前，父节点指向cur节点
				if (key > cur->_key) //比当前根节点大，走右边。
					cur = cur->_right;
				else if (key < cur->_key) //比当前根节点小，走左边
					cur = cur->_left;
				else
					return false; //默认二叉搜索树不允许重复值
			}
			cur = new Node(key);
			//这里虽然new了节点，但并未链接。
			//二叉树的链接是要父节点指向子节点。
			//但链接在左或右不知道，所以需要比较
			if (key > parent->_key)
				parent->_right = cur;
			else
				parent->_left = cur;
			return true;
		}

		bool Find(const K& key) {
			Node* cur = _root;
			while (cur) {
				if (key > cur->_key)
					cur = cur->_right;
				else if (key < cur->_key)
					cur = cur->_left;
				else
					return true;
			}
			return false;
		}

		bool Erase(const K& key) {
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else { //到这，cur指向被删除的节点
					if (cur->_left == nullptr) { //1.被删除节点的左子节点为空，即只有右子节点
						if (cur == _root) //还需要考虑被删除节点是根节点的情况
							_root = cur->_right;
						else {
							if (cur == parent->_left) //且被删除节点是其父节点的左子节点
								parent->_left = cur->_right;
							else //被删除节点是其父节点的右子节点
								parent->_right = cur->_right;
						}
					}
					else if (cur->_right == nullptr) { //2.被删除节点的右子节点为空，即只有左子节点
						if (cur == _root)
							_root = cur->_left;
						else {
							if (cur == parent->_left)
								parent->_left = cur->_left;
							else
								parent->_right = cur->_left;
						}
					}
					else { //3.左右都不为空
						//右树的最小节点(最左节点)
						//不能用递归或上方Find函数找到要删除的节点，
						//因为下方交换了两个节点后，现在已经不是二叉搜索树，
						//所以还需要最左节点的父节点。
						//如果右树的最左节点就是cur->_right，且parent初始化为空，
						//那么循环就不会进，导致parent为空(无法链接)，所以要将parent赋值为cur
						//parent = nullptr;
						parent = cur;
						Node* subLeft = cur->_right;//将被删除节点的右子节点作为起点
						while (subLeft->_left) { //找到最左下角的节点
							parent = subLeft;
							subLeft = subLeft->_left;
						}
						swap(cur->_key, subLeft->_key);//交换最左节点和被删除节点
						//虽然上方循环一直在找最左节点，但最左节点并不一定是其父节点的左子节点。
						//假设一种情况，(只描述树的一部分)，一棵树只有右子树，
						//且根节点的右子节点也只有右子树，要删除的是根节点，这时的最左节点是根的右子节点。
						//所以需要判断最左节点是其父节点的哪边
						if (subLeft == parent->_left)
							parent->_left = subLeft->_right;
						else
							parent->_right = subLeft->_right;
					}
					return true;
				}
			}
			return false;
		}

		//这种方式会导致在类外调用时找不到根节点
		//bt.InOrder();//调用中序遍历需要根节点，但不知道根节点是谁
		//void InOrder(Node* root) {
		//	if (root == nullptr)
		//		return;
		//	InOrder(root->_left);
		//	cour << root->_key << " ";
		//	InOrder(root->_right);
		//}

		void InOrder() {
			_InOrder(_root);
			cout << endl;
		}

		bool FindR(const K& key) { return _FindR(_root, key); }
		bool InsertR(const K& key) { return _InsertR(_root, key); }
		bool EraseR(const K& key) { return _EraseR(_root, key); }

		//BSTree() = default;//强制生成默认
		BSTree() {} //有缺省值初始化

		~BSTree() { //通过后序递归释放数，当不能递归析构函数
			Destroy(_root);
		}

		//拷贝构造同样是递归实现。以根、左子树、右子树的顺序拷贝。
		//对于其左右子树同样可以以相同方法实现。
		BSTree(const BSTree<K>& t) {
			_root = Copy(t._root);
		}

		BSTree<K>& operator=(BSTree<K> t) {
			swap(_root, t._root);
			return *this;
		}
	private:
		Node* _root = nullptr;

		//类里面可以获取根节点，所以在套一层，方便外面调用InOrder()
		void _InOrder(Node* root) {
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

		bool _FindR(Node* root, const K& key) {
			if (root == nullptr)
				return false;

			if (key > root->_key)
				_FindR(root->_right, key);
			else if (key < root->_key)
				_FindR(root->_left, key);
			else
				return true;
		}

		//bool _InsertR(Node* root, const K& key) { //这种方式虽然插入了节点，但没有链接
		//在递归中，每次递归调用都会创建新的栈帧，
		//每个栈帧中的引用参数都是独立的，可以绑定到不同的变量
		bool _InsertR(Node*& root, const K& key) {
			if (root == nullptr) {
				root = new Node(key);
				return true;
			}
			//当递归进行到上面这个条件时，当前这一层的递归是
			//_InsertR(root->_right, key);或_InsertR(root->_left, key);
			//也就是说，上一层的root->_left或root->_right引用了这层的root
			//在root这里创建节点自然就被链接上了。

			if (key > root->_key)
				return _InsertR(root->_right, key);
			else if (key < root->_key)
				return _InsertR(root->_left, key);
			else
				return false;
		}

		//这里的引用与插入类似，删除需要被删除节点的父节点，引用恰好能实现
		bool _EraseR(Node*& root, const K& key) {
			if (root == nullptr)
				return false;

			if (key > root->_key)
				return _EraseR(root->_right, key);
			else if (key < root->_key)
				return _EraseR(root->_left, key);
			else {
				//这里root指向的是被删除的节点，
				//同时，当前这一层的递归是_EraseR(root->_right, key);或_EraseR(root->_left, key);
				//也就是说，root上一层的root->_left或root->_right引用了这层的root。
				if (root->_left == nullptr) {
					Node* del = root;//记录被删除节点的指针
					//将root上一层的root->_left或root->_right指向了root下一层的_right
					root = root->_right;
					delete del;
					//如果删除的是根节点也没有问题，(走到这里时说明没有左子树)
					//因为root是根节点指针的引用，删除根节点
					//也可以理解为将根节点指针移动到根的右子节点
				}
				else if (root->_right == nullptr) {
					Node* del = root;
					root = root->_left;
					delete del;
				}
				else {
					Node* subLeft = root->_right;
					while (subLeft->_left)
						subLeft = subLeft->_left;
					swap(root->_key, subLeft->_key);

					return _EraseR(root->_right, key);
					//不能再整棵树中用递归解决，
					//因为交换了替换节点和被删除节点就不在满足二叉搜索树的性质了
					//但可以在小范围内使用递归(被删除节点右子节点作为根的树)，
					//被删除节点的右子树都比被删除节点大，替换节点是该右子树的最左节点(最小节点)，但依然比删除节点大
					//被删除节点与最左节点交换相当于换过来一个更小的值，依然能满足二叉搜索树的性质，即左子节点<根

					//当删除的是根节点时，根节点被换到了其右子数的最左节点，再将此时根的右子节点当做树的根来删除，
					//此时逻辑就回到上面的if (root->_left == nullptr)或else if (root->_right == nullptr)
					//也就是说第一层的root->_right是第二层root的别名，
					//第二层的root又指向了第三层的root->_left或root->_right
					//即第一层的root->_right指向了第三层的root->_left或root->_right
					//既删除了根节点又完成链接
				}
				return true;
			}
		}

		//void Destroy(Node* root) { //该方式导致root置空无效，形参的改变不影响实参
		void Destroy(Node*& root) { //改为引用
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

		Node* Copy(Node* root) {
			if (root == nullptr)
				return nullptr;

			Node* newRoot = new Node(root->_key);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);
			return newRoot;
		}
	};
}




//改造二叉搜索树为KV结构
//namespace key_value {
namespace kv {
	template <class K, class V>
	struct BSTreeNode { //数组只适合表示完全二叉树
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

		BSTreeNode(const K& key, const V& value)
			: _left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value) {
		}
	};

	template <class K, class V>
	class BSTree {
		typedef BSTreeNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value) {
			if (_root == nullptr) {
				_root = new Node(key, value);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				parent = cur; //cur往后遍历之前，父节点指向cur节点
				if (key > cur->_key) //比当前根节点大，走右边。
					cur = cur->_right;
				else if (key < cur->_key) //比当前根节点小，走左边
					cur = cur->_left;
				else
					return false; //默认二叉搜索树不允许重复值
			}
			cur = new Node(key, value);
			if (key > parent->_key)
				parent->_right = cur;
			else
				parent->_left = cur;
			return true;
		}

		Node* Find(const K& key) { //通过key找value
			Node* cur = _root;
			while (cur) {
				if (key > cur->_key)
					cur = cur->_right;
				else if (key < cur->_key)
					cur = cur->_left;
				else
					return cur;
			}
			return nullptr;
		}

		bool Erase(const K& key) {
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else { //到这，cur指向被删除的节点
					if (cur->_left == nullptr) { //1.被删除节点的左子节点为空，即只有右子节点
						if (cur == _root) //还需要考虑被删除节点是根节点的情况
							_root = cur->_right;
						else {
							if (cur == parent->_left) //且被删除节点是其父节点的左子节点
								parent->_left = cur->_right;
							else //被删除节点是其父节点的右子节点
								parent->_right = cur->_right;
						}
					}
					else if (cur->_right == nullptr) { //2.被删除节点的右子节点为空，即只有左子节点
						if (cur == _root)
							_root = cur->_left;
						else {
							if (cur == parent->_left)
								parent->_left = cur->_left;
							else
								parent->_right = cur->_left;
						}
					}
					else { //3.左右都不为空
						parent = cur;
						Node* subLeft = cur->_right;
						while (subLeft->_left) {
							parent = subLeft;
							subLeft = subLeft->_left;
						}
						swap(cur->_key, subLeft->_key);
						if (subLeft == parent->_left)
							parent->_left = subLeft->_right;
						else
							parent->_right = subLeft->_right;
					}
					return true;
				}
			}
			return false;
		}

		void InOrder() {
			_InOrder(_root);
			cout << endl;
		}

	private:
		Node* _root = nullptr;

		//类里面可以获取根节点，所以在套一层，方便外面调用InOrder()
		void _InOrder(Node* root) {
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	};
}